package com.mxw.算法之美.a1数组;

public class S02MyArrayList <E> {

    // 存储数据
    private E[] data;

    private int size;

    private static final int INIT_CAP = 1;

    private S02MyArrayList(int initCapacity) {
        data = (E[]) new Object[initCapacity];
        size=0;
    }

    private S02MyArrayList() {
        this(INIT_CAP);
    }

    // 扩容
    private void resize(int newCap) {
        E[] temp= (E[]) new Object[newCap];

        // 复制
        for (int i = 0; i < size; i++) {
            temp[i] = data[i];
        }
        data = temp;
    }

    private void checkPositionIndex(int index) {
        if (index < 0 || index > size){
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }

    // 尾巴插入
    public void addEnd(E e) {
        int cap= data.length;
        if (size==cap) {
            resize(2*cap);
        }
        data[size]=e;
        size++;
    }

    public void addFirst(E e) {
        add(0, e);
    }

    // 往第几个位置插入
    public void add(int index, E e) {

        // 位置是否正确
        checkPositionIndex(index);

        // 容量判断
        int cap= data.length;
        if (size==cap) {
            resize(2*cap);
        }

        // 给新元素挪出位置
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }

        // 插入新元素
        data[index] = e;
        size++;
    }

    public E remove(int index) {
        // 检查索引越界
        int cap = data.length;
        // 可以缩容，节约空间
        if (size == cap / 4) {
            resize(cap / 2);
        }

        E deletedVal = data[index];

        // 往前移动
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        data[size - 1] = null;
        size--;

        return deletedVal;
    }


}
